#include<iostream>
#include<vector>
#include<algorithm>
#include<priority_queue>
using namespace std;

class Solution {
public:
    void sortColors(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        // int n = nums.size();
        // int ptr = 0;
        // for (int i = 0; i < n; ++i) {
        //     if (nums[i] == 0) {
        //         swap(nums[i], nums[ptr]);
        //         ++ptr;
        //     }
        // }
        // for (int i = ptr; i < n; ++i) {
        //     if (nums[i] == 1) {
        //         swap(nums[i], nums[ptr]);
        //         ++ptr;
        //     }
        // }
    }

};

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        vector<int> ans;
        ans.reserve(30);
        sort(stock.begin(), stock.end());
        for (int i = 0; i < cnt; i++) {
            ans.push_back(stock[i]);
        }
        return ans;
    }
};

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = -1, right = nums.size();
        int i = 0;
        while (i < right) {
            if (nums[i] == 0) {
                swap(nums[i], nums[++left]);
                i++;
            }
            else if (nums[i] == 1)i++;
            else if (nums[i] == 2) {
                swap(nums[i], nums[--right]);
            }
        }
    }

};


class Solution {
public:

    void MyQuickSort(vector<int>& arr, int begin, int end)
    {
        if (begin >= end) return;
        swap(arr[begin], arr[rand() % (end - begin) + begin]);
        int posk = begin;
        int left = begin, right = end + 1;
        int i = begin + 1;
        while (i < right) {
            if (arr[i] < arr[posk]) {
                swap(arr[i], arr[++left]);
                i++;
            }
            else if (arr[i] == arr[posk]) i++;
            else if (arr[i] > arr[posk]) {
                swap(arr[i], arr[--right]);
            }
        }
        swap(arr[posk], arr[i - 1]);

        MyQuickSort(arr, begin, left);
        MyQuickSort(arr, i, end);
    }

    vector<int> sortArray(vector<int>& nums) {
        MyQuickSort(nums, 0, nums.size() - 1);
        return nums;
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq;
        for (int i = 0; i < nums.size(); i++) {
            pq.push(nums[i]);
        }
        for (int i = 1; i < k; i++) {
            pq.pop();
        }
        return pq.top();
    }
};

class Solution {
public:

    int MyQuickFind(vector<int>& arr, int k, int begin, int end)
    {
        if (begin == end) return arr[end];
        int key = arr[begin + rand() % (end - begin + 1)];
        int left = begin - 1, right = end + 1;
        int i = begin;
        while (i < right) {
            if (arr[i] < key)
                swap(arr[i++], arr[++left]);
            else if (arr[i] == key) i++;
            else if (arr[i] > key)
                swap(arr[i], arr[--right]);
        }
        int c = end - right + 1;
        int b = right - left - 1;
        if (c >= k) return MyQuickFind(arr, k, right, end);
        else if (b + c >= k) return key;
        else return MyQuickFind(arr, k - b - c, begin, left);
    }

    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        return MyQuickFind(nums, k, 0, nums.size() - 1);
    }
};

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (auto& e : stock) {
            pq.push(e);
        }
        vector<int> ans;
        for (int i = 0; i < cnt; i++) {
            ans.push_back(pq.top());
            pq.pop();
        }
        return ans;
    }
};

class Solution {
public:

    void MyQuickSort(vector<int>& arr, int k, int begin, int end)
    {
        if (begin >= end)return;
        int key = arr[begin + rand() % (end - begin + 1)];
        int left = begin - 1, right = end + 1;
        int i = begin;
        while (i < right) {
            if (arr[i] < key)
                swap(arr[i++], arr[++left]);
            else if (arr[i] == key) i++;
            else if (arr[i] > key)
                swap(arr[i], arr[--right]);
        }
        int a = left - begin + 1;
        int b = right - left - 1;
        if (a >= k) MyQuickSort(arr, k, begin, left);
        else if (a + b >= k) return;
        else MyQuickSort(arr, k - a - b, right, end);
    }

    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand(time(NULL));
        MyQuickSort(stock, cnt, 0, stock.size() - 1);
        return vector<int>(stock.begin(), stock.begin() + cnt);
    }
};